#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int dp_func(vector<int>nums){
        vector<int>dp = vector<int>(nums.size()-1,0);
        dp[0] = nums[0];
        for(int i=1;i<nums.size()-1;i++){
            //构建dp转移方程
            if(i>=2)
                dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
            else
                dp[i] = max(dp[i-1], nums[i]);
        }
        return max(dp[nums.size()-2],dp[nums.size()-3]);
    }
    int rob(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        if(nums.size()==1)  //这三种情况可以直接判断，不需要dp
            return nums[0];
        if(nums.size()==2)
            return max(nums[0], nums[1]);

        vector<int>orig_nums = nums;
        reverse(nums.begin(), nums.end());
        //正向遍历一次，逆向遍历一次
        return max(dp_func(orig_nums), dp_func(nums));
    }
};
int main(int argc, char* argv[]){
    Solution *s = new Solution();
    vector<int> nums = {1,2,3,1};
    cout<<s->rob(nums)<<endl;
    return 0;
}